//---------------------------------------------------------
//	hash tree definition
//---------------------------------------------------------
#ifndef HASHTREE_H
#define HASHTREE_H
#pragma pack(push,1)

#include "hash/hash.h"

//---------------------------------------------------------
//	an item in the hash tree
//---------------------------------------------------------
class HashTreeItem
{
public:
	HashTreeItem	*branches[2];
	HASH			hashValue;
	void			*pData;

	void	Enumerate( void (*fn)( void *pData ) ) const;
};

//---------------------------------------------------------
//	a static hash tree
//---------------------------------------------------------
class StaticHashTree
{
public:
	StaticHashTree() : m_nItems(0), m_root(null)	{	/*empty*/	}
	~StaticHashTree()	{	/*empty*/	}

	// set up the static hash tree
	void			SetData( u32 nItems, HashTreeItem *pItems );

	// searching the tree
	void			*FindByHash( HASH byHash ) const;

	// enumerate items
	inline void		Enumerate( void (*pfn)( void *pData ) ) const
	{
		if( m_root )	m_root->Enumerate(pfn);
	}
	inline	u32		GetNItems() const
	{
		return m_nItems;
	}

protected:
	u32				m_nItems;
	HashTreeItem	*m_root;
};


//---------------------------------------------------------
//	the hash tree
//---------------------------------------------------------
class HashTree : public StaticHashTree
{
public:
	HashTree() : StaticHashTree(), m_allocatedItems(null),m_freeItems(null)	{	/*empty*/	}
	~HashTree();

	// clear the hash tree
	void	Clear( bool freeMemory=false );

	// staticly populate the free list
	void	AddFreeItems( HashTreeItem *pItems, u32 nItems );

	// functions by hash
	bool	AddByHash( HASH hashValue, void *pData );
	bool	RemoveByHash( HASH hashValue );

	// functions by type
	template <class X>
	inline	bool	Add( X *pData )
	{
		return AddByHash(pData->MakeHash(),pData);
	}

	template <class X>
	inline	bool	Remove( const X *pData )
	{
		return RemoveByHash(pData->MakeHash());
	}

protected:

	// free item management
	void				CreateEmptyItems( u32 nItems );
	HashTreeItem*		GetFreeItem();

	// find where in the tree an item should go
	HashTreeItem**		GetPlacement( HASH hash  );

	// recursively add all items from a given node into a linear list
	HashTreeItem**		MakeLinear( HashTreeItem *pItem, HashTreeItem **ppList );

	// the hash tree
	HashTreeItem	*m_allocatedItems;
	HashTreeItem	*m_freeItems;
};

#pragma pack(pop)
#endif
